package test.algorithms;

public class Palindrome {

	public static void main(String[] args) {

		int amount = 100;

		StringBuffer buf = new StringBuffer();
		for (int i = 0; i < amount; i++) {
			buf.append('a');
		}

		for (int i = 1; i <= amount; i++) {
			System.out.println(getLongestPalindrome(buf.toString().substring(0, i)));
		}
	}

	public static String getLongestPalindrome(String str) {

		int comparisons = 0;
		
		if (str == null) {
			return null;
		}

		String longestPalindrome = "";

		for (int i = 0; i < str.length() - 2; i++) {

			int h1, h2;

			// Identify first the middle part of a palindrome : 'xyx', 'xx'
			if (str.charAt(i) == str.charAt(i + 2)) { // case 'xyx'

				comparisons++;
				h1 = i;
				h2 = i + 2;

			} else if (str.charAt(i) == str.charAt(i + 1)) { // case 'xx'

				comparisons++;
				h1 = i;
				h2 = i + 1;

			} else { // continue with next char if around chars at i, i+1, and
						// i+2 there is no a palindrome

				continue;
			}

			// Detect how big is this palindrome (take care of string
			// boundaries)
			h1--;
			h2++;

			while (h1 >= 0 && h2 < str.length() && str.charAt(h1) == str.charAt(h2)) {

				comparisons += 3;
				h1--;
				h2++;
			}

			// Save the new palindrome found if it longest than the previous
			// one, if any
			// This is going to keep only the first one for a determined lenght!
			if (h2 - h1 - 1 > longestPalindrome.length()) {
				
				comparisons++;
				longestPalindrome = str.substring(h1 + 1, h2);
			}
		}

		return "" + comparisons ;//longestPalindrome;
	}
}
